package _2_leetcode_21_40._33搜索旋转排序数组;

/**
 * User: Mazexal
 * Date: 2021/1/19
 */
public class Solution {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 6, 7, 0, 1, 2};
        System.out.println(search(arr, 0));

        int[] arr1 = new int[]{4, 5, 6, 7, 0, 1, 2};
        System.out.println(search(arr1, 3));

        int[] arr2 = new int[]{1};
        System.out.println(search(arr2, 0));
    }

    // 还是使用二分法, 不过稍微做了点调整
    public static int search(int[] nums, int target) {
        if (nums.length < 5) {
            for (int i = 0; i < nums.length; i++) {
                if (target == nums[i]) {
                    return i;
                }
            }
            return -1;
        } else {
            int l = 0;
            int r = nums.length - 1;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[0] <= nums[mid]) {
                    if (nums[0] <= target && target < nums[mid]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else {
                    if (nums[mid] < target && target <= nums[nums.length - 1]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }

            }
            return -1;
        }
    }
}
